Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
My Solution
You can solve this by first creating a sentinel node for the start of the merged list. We will always return the next node of the sentinel node as the head of the merged list. We then have two pointers for the two lists and iterate. We add the smaller of the two pointers at every iteration and advance the pointer for that list. When we have exhausted all the elements for one of the lists, we just add all the elements of the other list one by one to our merged list. We then return the next node of the sentinel to return the head of the merged list.
The time complexity is O(m+n), where m is the size of list1 and n is the size of list2. The space complexity is O(m+n) as well because we are creating new nodes for the merged list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode sent = new ListNode(0);
ListNode n = sent;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
n.next = new ListNode(list1.val);
list1 = list1.next;
}
else {
n.next = new ListNode(list2.val);
list2 = list2.next;
}
n = n.next;
}
while (list1 != null) {
n.next = new ListNode(list1.val);
n = n.next;
list1 = list1.next;
}
while (list2 != null) {
n.next = new ListNode(list2.val);
n = n.next;
list2 = list2.next;
}
return sent.next;
}
}